package q710_BlackList;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

/*
最简单的想法：
使用一个set存储所有黑名单中的数字 并且不超过n
每次需要取出时，即反复的使用random生成并检验是否在set中
直到满足条件为止
（该方法会超时）
 */
public class Solution_1 {
    Set<Integer> set;
    Random random;
    int range;
    public Solution_1(int n, int[] blacklist) {
        set = new HashSet<>();
        range = n;
        random = new Random();
        Arrays.sort(blacklist);
        for (int i = 0; i < blacklist.length && blacklist[i] < n; ++i) {
            set.add(blacklist[i]);
        }
    }

    public int pick() {
        int ans = random.nextInt(range);
        while (set.contains(ans)) {
            ans = random.nextInt(range);
        }
        return ans;
    }
}
